package LeetCode刷题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-11 19:31
 * @description: Functions of this class is
 *
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 * 回文串 是正着读和反着读都一样的字符串。
 *
 * 示例 1：
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 *
 *
 * 提示：
 * 1 <= s.length <= 16
 * s 仅由小写英文字母组成
 *
 **/
public class No动态规划分割回文符 {
    public static void main(String args[]){
        System.out.println(partition("aab"));
    }
    private static List<List<String>> partition(String s) {
        List<List<String>> ans=new ArrayList<>();
        List<String> sub=new ArrayList<>();
        /**
        boolean flag[][]=new boolean[s.length()][s.length()];

        //先把所有flag集合中的数字都赋值位真
        for(int i=0;i<s.length();i++){
            Arrays.fill(flag[i],true);//即一开始假设所有的子串都为回文串？
        }
        //用双指针开始逐一判断是否为回文串,采用了动态规划
        for(int i=s.length()-1;i>=0;i--){
            for(int j=i+1;j<s.length();j++){
                flag[i][j]=(s.charAt(i)==s.charAt(j))&&flag[i+1][j-1];
                //判断当前子串是否为回文串的依据是：当前双指针下的两个字符相等，同时上一个和该子串链接的子串也是回文串
            }
        }
        //判断完成后，开始递归回溯，找寻所有的子串
         **/
        dfs(s,0,sub,ans);
        return ans;
    }
    private static void dfs(String s,int index,List<String> sub,List<List<String>> ans){
        if(index==s.length()){
            //说明一个字串判断完成
            ans.add(new ArrayList<>(sub));
            return;
        }

        //否则继续判断
        for(int j=index;j<s.length();j++){
            String temp=s.substring(index,j+1);
            if(judge(temp)){
                //如果该区间内的子串是回文串的话
                sub.add(temp);//则截取index到j下标的子串
                dfs(s,j+1,sub,ans);//继续递归下一位j
                sub.remove(sub.size()-1);//回退的时候则删除递归前加入进去的那个子串，防止出错
            }
        }
    }
    //a a b
    private static boolean judge(String s){
        int i=0;
        int j=s.length()-1;
        while (i<j){//在字符串内判断
            if(s.charAt(i)!=s.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}